\documentclass[12pt, a4paper]{article}

% Configuración de márgenes de las páginas
	\usepackage{a4wide}

% Paquete de acentos para Linux
	\usepackage[utf8]{inputenc}

% Paquete para reconocer la separación en sílabas en español
	\usepackage[spanish]{babel}

% Paquetes especiales para el TP
	\usepackage{caratula}

%	Paquete para simbolos matemáticos
	\usepackage{amssymb}			
	\usepackage{amsmath}

% Paquete para armar índices
	\usepackage{makeidx}
	\makeindex

% Más espacio entre líneas
	\parskip=1.5pt

% Otros paquetes
	\usepackage{graphicx}
	\usepackage{float}
	\usepackage{listings}
	\usepackage{color}
	\usepackage{url}
	\definecolor{lnk}{rgb}{0,0,0.4}
	\usepackage[colorlinks=true,linkcolor=lnk,citecolor=blue,urlcolor=blue]{hyperref}

% Importo los comandos personalizados
	\input{comandos_pers.tex}

	\lstset{language=C,basicstyle=\small\tt,keywordstyle=\bf,tabsize=3,breaklines=true,linewidth=16cm,postbreak={\mbox{$\rightsquigarrow$}},prebreak={\mbox{$\rightsquigarrow$}}}


\begin{document}

% Carátula
	\titulo{Trabajo Práctico Nº1}
	\fecha{11 de Mayo de 2010}
	\materia{Problemas Algoritmos y Programación}
	\grupo{  }
	\integrante{Allekotte, Kevin}{490/08}{kevinalle@gmail.com}
	%\integrante{Di Pietro, Carlos A.}{126/08}{cdipietro11@gmail.com}
	\integrante{Fischer, Thomas}{489/08}{tfischer@dc.uba.ar}
	\maketitle

	\newpage		\printindex \tableofcontents
	
	
%	\newpage
%		\begin{usection}{10362. Trains}
%			\url{http://uva.onlinejudge.org/external/103/10362.html}\\
%			
%			
%			
%			\begin{usubsection}{Idea}
%				
%			\end{usubsection}
%			
%			\begin{usubsection}{Complejidad}
%				
%			\end{usubsection}
%		\end{usection}


	\newpage
		\begin{usection}{10462. Is There A Second Way Left?}
			\url{http://uva.onlinejudge.org/external/104/10462.html}\\
			
			Nasa's neighbors have decided to connect themselves over a network, but he wants to minimize the total cost of cable required. He wants to know the second best cost for the project.
			
			\begin{usubsection}{Idea}
				Sea un grafo en el cual los nodos representan a las computadoras y las aristas son las conexiones entre ellas con el costo de la conexion como su valor. Las conexiones son bidireccionales asi que se trata de un grafo no dirigido.
				Las conexiones que garantizan que todas las computadoras esten conectadas es un grafo conexo inducido que tiene todos los nodos del grafo original. Como queremos minimizar el costo, este grafo es un árbol.
				
				El árbol generador mínimo (AGM) es el arbol que es subgrafo del grafo original, tiene todos los nodos, es un árbol, y es de peso mínimo. Lo que queremos encontrar es un arbol generador de costo mínimo que sea distinto del AGM del grafo.

				\medskip
				Para esto implementamos el algoritmo de Kruskal para encontrar el AGM. Nuestro objetivo es encontrar un árbol distinto al AGM y que sea el menor de todos los posibles.
				Si calculamos el AGM del grafo que resulta de sacar una arista del grafo (de las que pertenecían al AGM), obtenemos un árbol generador del grafo original, distinto de su AGM.
				Nuestro método consiste en calcular todos los árboles de esta forma y quedarnos con el que minimice el costo.
				
				\medskip
				Sin embargo, antes de hacer esto hay que revisar que todas las computadoras puedan ser conectadas (que el grafo sea conexo) y que exista más de una forma de hacerlo ($m+1>n$). Esto lo logramos con un BFS y con una cuenta respectivamente.
			\end{usubsection}
			
			\begin{usubsection}{Complejidad}
				La complejidad del algoritmo de Kruskal es \Ode{E log(E)}. El BFS es \Ode{E+V}. El AGM tiene $V-1$ aristas. El Algoritmo usa Kruskal sobre el grafo una vez por cada arista del AGM.
				Entonces el complejidad total es de $\Ode{E+V}+\Ode{E log(E)}+V\times\Ode{E log(E)} \subset \Ode{V E log(E)}$
			\end{usubsection}
		\end{usection}
		
	
	\newpage
		\begin{usection}{10806. Dijkstra, Dijkstra}
			\url{http://uva.onlinejudge.org/external/108/10806.html} \\
			
			\begin{usubsection}{Idea}
				La idea del algoritmo es encontrar los dos caminos
				que sumen menos peso en el grafo (conjuntamente),
				usando el algoritmo de Bellmann$-$Ford para caminos
				mínimos.

				El problema es que no necesariamente un camino
				del resultado es un camino mínimo del grafo original,
				ya que elegirlo compromete en algunos casos la
				elección del segundo.

				No obstante el primer paso del algoritmo es encontrar
				el camino mínimo en el grafo original, ya que luego
				planteamos una corrección para encontrar los caminos
				que sumen menos conjuntamente.

				La idea es encontrar un grafo de aumento en el grafo
				sin el camino mínimo, pero con las aristas usadas en
				sentido inverso con el mismo peso pero negativas (una especie de grafo residual).
				Si el camino mínimo en este nuevo grafo pasase por éstas,
				estaría corrigiendo el primer camino de manera de
				minimizar el flujo total.

				Parta encontrar el segundo camino mínimo, usamos
				nuevamente el algoritmo de Bellmann$-$Ford ya que
				tenemos aristas de peso negativo en el grafo.

				Luego, si encontramos un camino original y uno nuevo,
				sumamos los dos resultados y esa es la respuesta. \\

				Este problema nos sigue dando Wrong$-$answer en el juez
				online por un problema que aún no pudimos descubrir

			\end{usubsection}
			
			\begin{usubsection}{Complejidad}

				La complejidad del algoritmo de Bellmann-Ford es
				$O(n^3)$, ya que iteramos $n-1$ veces sobre toda la
				matriz de pesos que tiene un tamaño $O(n^2)$.
				Este algoritmo lo corremos dos veces y ademas hacemos la
				actualización del grafo para crear la red residual,
				lo cuál lleva $O(n)$ en el caso que el primer camino
				mínimo pase por todos los nodos.

				Luego la complejidad nos queda $2O(n^3) + O(n) = O(n^3)$,
				donde n es la cantidad de estaciones del problema y m
				es la cantidad de calles.

			\end{usubsection}
		\end{usection}
	
	\newpage
		\begin{usection}{1759. Sokoban}
			\url{https://br.spoj.pl/problems/CUBO/} \\
			
			\begin{usubsection}{Idea}

				El sokoban, como muchos problemas de juegos,
				se puede modelar con un grafo de estados, donde un nodo
				en el mismo representa un estado particular del juego,
				y las aristas representan las transiciones entre los
				distintos estados.

				En particular en el sokoban, tomamos como estados la
				posición del cubo y la del jugador. Para pasar de un
				estado del juego al siguiente, podemos empujar el
				cubo en alguna de las 4 direcciones permitidas
				(de ser posible), obteniendo así un nuevo estado.
				O sea que cada nodo tiene a lo sumo 4 aristas o posibles
				transiciones de estado.

				Luego para encontrar el camino mínimo del cubo hasta su
				objetivo, basta con encontrar el camino mínimo en el
				grafo de estados mencionado. El costo de cada transición
				(peso de la arista asociada) es 1 en todos los casos,
				ya que lo que quiero minimizar son los movimientos del
				cubo en primer lugar, de los cuáles se efectúa 1 por
				transición.

				Como no tenemos una función de costo que nos permita
				usar Dijkstra u otro algoritmo de camino mínimo que la
				requiera, usamos BFS para encontrarlo.

				Un detalle es que el estado del cubo solo es marcado
				como visitado con respecto a la dirección en que se
				movió, ya que a veces es necesario pasar dos veces por
				la misma posición del cubo, pero no lo es pasar haciendo
				el mismo movimiento ya que estaríamos pasando por un
				ciclo en el grafo de estados.

				Para cada transición calculamos, además, el camino
				mínimo que le lleva al jugador posicionarse en el lugar
				para empujar el cubo (si es que puede). Así logramos
				minimizar en segundo lugar la cantidad de movimientos
				del jugador. Este camino mínimo. por las mismas razones,
				también lo buscamos con BFS.

				Este problema está dando time-limit-exceeded en el juez
				online, por lo que todavía tenemos que pensar alguna
				optimización para hacerle.
				Sobre todo se vuelve lento cuando las grillas tienen
				pocas paredes y son muy grandes (mas grande que 10x10).

			\end{usubsection}

			\begin{usubsection}{Complejidad}

				La complejidad del BFS del cubo es $O(4*n)$ ya que la
				cantidad de vecinos de un nodo esta acotada por 4.
				A su vez, el costo de mover al jugador con BFS también
				tiene el mismo costo por la misma razón.

				Esto nos da una complejidad de $O(n)*O(n) = O(n^2)$, lo cuál resulta extraño ya que nos excedemos en tiempo de ejecución, y $O(n^2)$ suele ser una buena complejidad.

			\end{usubsection}
		\end{usection}

	\newpage
		\begin{usection}{Apendix: Code listings}

			%\begin{usubsection}{10362. Trains}
			%	\lstinputlisting{../10362/10362.cpp}
			%\end{usubsection}
			
			%\newpage
			\begin{usubsection}{10462. Is There A Second Way Left?}
				\lstinputlisting{../10462/10462.cpp}
			\end{usubsection}
			
			\newpage
			\begin{usubsection}{10806. Dijkstra, Dijkstra}
				\lstinputlisting{../10806/10806.cpp}
			\end{usubsection}
			
			\newpage
			\begin{usubsection}{1759. Sokoban}
				\lstinputlisting{../1759/1759.cpp}
			\end{usubsection}
		\end{usection}


\end{document}

